package arithmetic;
//你有27块钱，分别有2,5,7的面值，问用最少得硬币组成27
//转移方程为：f[i] = min(f[i-2]+1,f[i-5]+1,f[i-7]+1)
public class Dp1 {
//    int[] A,int M分别表示2,5,7和27
    public static int coinChange(int[] A,int M){
        int n = A.length;//长度
        int[] f = new int[M+1];//这个数组存放计算过的数剧
        int i,j;
        f[0] = 0;
        for (i = 1; i <=M ; ++i) {
//            初始化让每个数组存放的都是极大值
            f[i] = Integer.MAX_VALUE;
            for ( j = 0; j <n ; ++j) {
//                使用2,5,7三个面值去遍历M得到最小值f[1]
                if(i>=A[j]&&f[i-A[j]]!=Integer.MAX_VALUE&&f[i-A[j]]+1<f[i]){
                    f[i] = f[i-A[j]]+1;
                }

            }
        }
        if (f[M]==Integer.MAX_VALUE){
            return -1;
        }else {
            return f[M];
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{2,5,7};
        System.out.println(coinChange(arr,27));
    }
}
/*
* 我们使f[负数]为无穷大,如f[-1] = Integer.MAX_VALUE
* f[0] = 0
* f[1] = min(f[-2]+1,f[-5]+1,f[-7]+1)三个都是无穷大，所以没有
* f[2] = min(f[0]+1,f[-3]+1,f[-5]+1)最小值为f[0]+1,等于1
* f[3] = min(f[1]+1,f[-2]+1,f[-2]+1)三个都是无穷大，所以没有
* f[4] = min(f[2]+1,f[-1]+1,f[-3]+1)最小值为f[2]+1==>f[0]+1+1=2
* f[5] = min(f[3]+1,f[0]+1,f[-2]+1)最小值为f[0]+1=1
* */